package leetcode.editor.cn.q1_300.q100;

import leetcode.editor.cn.util.graph.GraphUtil;
import leetcode.editor.cn.util.graph.Node;

import java.util.*;

/**
 * @author qidi
 * @date 2022-01-12 15:45:56
 */
class Q0133_CloneGraph {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public Node cloneGraph(Node node) {
            if (node == null) return null;
            Set<Integer> used = new HashSet<>();
            Deque<Node> deq = new ArrayDeque<>();
            deq.add(node);

            Map<Integer, Node> map = new HashMap<>();

            Node ans = null;
            while (!deq.isEmpty()) {
                Node poll = deq.poll();
                int pVal = poll.val;
                map.putIfAbsent(pVal, new Node(pVal));
                Node cur = map.get(pVal);
                if (ans == null) ans = cur;
                for (Node n : poll.neighbors) {
                    int nVal = n.val;
                    if (!used.contains(nVal)) {
                        if (!deq.contains(n)) deq.add(n);
                        map.putIfAbsent(nVal, new Node(nVal));
                        Node cn = map.get(nVal);
                        cur.neighbors.add(cn);
                        cn.neighbors.add(cur);
                    }
                }
                used.add(pVal);
            }
            return ans;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0133_CloneGraph().new Solution();
        GraphUtil util = GraphUtil.getInstance();
        Node node = util.generateFromArray("[[2,4,5],[1,3],[2,4,5],[1,3],[1,3]]");
        Node n = solution.cloneGraph(node);
        System.out.println(util.toString(n));
    }
}